//
//  SortSolution.hpp
//  leetcode
//
//  Created by Ellie on 2021/2/7.
//  Copyright © 2021 Ellie. All rights reserved.
//

#ifndef SortSolution_hpp
#define SortSolution_hpp

#include <stdio.h>
#include "DataDefine.h"
#include <queue>
#include <unordered_map>
#include <string>
#include <stack>
#include <vector>
#include <deque>
#include <iostream>
#include <sstream>

using namespace std;

class SortSolution
{
public:
    // 148. Sort List Merge Sort or Quick Sort
    ListNode* sortBubble(ListNode* head);
    // 147. Insertion Sort List
    ListNode* sortInsertion(ListNode* head);
    ListNode* sortMerge(ListNode* head);
    ListNode* sortMerge(ListNode* l1, ListNode* l2);
    ListNode* getMedian(ListNode* left, ListNode* right);
    
    vector<int> sortBubble(vector<int>& input);
    vector<int> sortSelection(vector<int>& input);
    vector<int> sortInsertion(vector<int>& input);
    vector<int> sortShell(vector<int>& input);
    void sortMerge(vector<int>& input);
    void sortMerge(vector<int>& input, int low, int high);
    void merge(vector<int>& input, int low, int mid, int high);
    void mergestable(vector<int>& input, int low, int mid, int high);
    void sortQuick(vector<int>& input);
    void sortQuick(vector<int>& input, int low, int high);
    int partition(vector<int>& input, int low, int high);
    int random_partition(vector<int>& input, int low, int high);
    
    void sortwithpriority_queue(vector<int>& nums, bool ascendorder);
    void sortHeap(vector<int>& nums, bool ascendorder);
    
    // 215. 数组中的第K个最大元素
    int findKthLargest(vector<int>& nums, int k);
    int findKthLargestPartition(vector<int>& nums, int low, int high, int k);
    // 347. 前 K 个高频元素
    vector<int> topKFrequent(vector<int>& nums, int k);
    // 4. 寻找两个正序数组的中位数 HARD
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2);
    // 973. 最接近原点的 K 个点
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K);
    // 692. 前K个高频单词 频率相同按照字母顺序排序
    vector<string> topKFrequent(vector<string>& words, int k);
};
// 排序算法


// 堆
// 索引从1开始，i节点的左节点2*i，右节点2*i+1
// 索引从0开始，i节点的左节点2*i+1，右节点2*i+2
// 堆的重建：叶子节点不用加入堆化，从倒数第二层开始 n/2-1，或者是n/2-1
class myheap
{
private:
    vector<int> nums;
    int count;
    int n;
public:
    void heapsortascend(vector<int>& nums);
    void heapsortdescend(vector<int>& nums);
    
    // interface
    void buildMaxHeap(vector<int>& nums, int heapsize);
    void maxHeapify(vector<int>& nums, int i, int heapsize);
    
    void buildMinheap(vector<int>& nums, int heapsize);
    void minHeapify(vector<int>& nums, int i, int heapsize);
};

#endif /* SortSolution_hpp */
